Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)

Increasing and Decreasing

比赛时漏看第三个条件，搞半天。而且似乎倒着减会比较容易做（差不多）。

public static void solve() {
    int x = io.nextInt(), y = io.nextInt(), n = io.nextInt();
    int z = (1 + n - 1) * (n - 1) / 2;
    if (z > y - x) {
        io.println(-1);
        return;
    }
    io.print(x + " ");
    int d = x + y - x - z;
    for (int i = n - 1; i >= 1; i--) {
        d += i;
        io.print(d + " ");
    }
    io.println();
}

Swap and Reverse

找规律。第一个操作表明奇数下标相互连通，偶数下标相互连通。第二个操作，如果 \(k\) 是奇数，则连通性不会改变，分别对奇偶字母排序，然后构造即可；如果 \(k\) 是偶数，则奇数下标和偶数下标相互连通，对所有字母排序即可。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    char[] s = io.next().toCharArray();
    if (k % 2 == 0) {
        Arrays.sort(s);
        io.println(new String(s));
    } else {
        PriorityQueue<Character> list1 = new PriorityQueue<>();
        PriorityQueue<Character> list2 = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) list1.add(s[i]);
            else list2.add(s[i]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) sb.append(list1.poll());
            else sb.append(list2.poll());
        }
        io.println(sb.toString());
    }
}

Divisor Chain

比赛时瞎猜 AC 的，当时是想从 \(1\) 开始构造到 \(x\)，过程比答案复杂。正解是从 \(x\) 一直减去最低有效位的一（必定是除数），直到 \(x\) 等于 \(2\) 的幂（只剩一个一），然后让 \(x\) 一直减去 \(\frac{x}{2}\) 即可。

public static void solve() {
    int x = io.nextInt();
    List<Integer> ans = new ArrayList<>();
    ans.add(x);
    while ((x & (x - 1)) != 0) {
        x &= (x - 1);
        ans.add(x);
    }
    while (x != 1) {
        x /= 2;
        ans.add(x);
    }
    io.println(ans.size());
    for (int y : ans) {
        io.print(y + " ");
    }
    io.println();
}

Matrix Cascade

使用差分数组维护从上到下的翻转次数，需要注意的是正负需要分开存，正数每层左移一位，负数每层右移一位。PS：这题 \(p\) 和 \(q\) 总是写错，Debug 很久。以及大佬的代码看不懂。

public static void solve() {
    int n = io.nextInt();
    char[][] a = new char[n][];
    for (int i = 0; i < n; i++) {
        a[i] = io.next().toCharArray();
    }
    int ans = 0;
    int[] p = new int[n + 1];
    int[] q = new int[n + 1];
    int[] sum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] - '0' != sum[j + 1] % 2) {
                ans++;
                p[j] ^= 1;
                q[j + 1] ^= 1;
            }
        }
        p[0] ^= p[1];
        for (int j = 1; j < n; j++) {
            p[j] = p[j + 1];
        }
        q[n] ^= q[n - 1];
        for (int j = n - 1; j > 0; j--) {
            q[j] = q[j - 1];
        }
        for (int j = 0; j < n; j++) {
            sum[j + 1] = sum[j] ^ p[j] ^ q[j];
        }
    }
    io.println(ans);
}

Guess Game

有点难以描述，超出能力范围了。这是一个比较好理解的做法，分别考虑每一位。从最低位开始，如果前缀相同，那么就计算当前位 \(0\) 和 \(1\) 的个数，只有爱丽丝拿 \(1\)，鲍勃拿 \(1\) 或 \(0\) 的情况，当前位才会多走一轮。初始时，设置答案为 \(n \times n\)，因为每个组合至少会走一轮。最后需要使用快速幂求 \(n\) 的逆元。

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    Arrays.sort(a);
    long ans = (long) n * n;
    for (int t = 0; t < 30; t++) {
        for (int l = 0, r = 0; l < n; l = r) {
            int[] cnt = new int[2];
            while (r < n && a[l] / 2 == a[r] / 2) {
                cnt[a[r] % 2]++;
                r++;
            }
            ans += (long) cnt[1] * (cnt[1] + cnt[0]);
        }
        for (int i = 0; i < n; i++) {
            a[i] /= 2;
        }
    }
    ans = ans % MOD * pow(n, MOD - 2) % MOD * pow(n, MOD - 2) % MOD;
    io.println(ans);
}

private static int pow(int a, int n) {
    long res = 1, x = a;
    while (n != 0) {
        if (n % 2 == 1) {
            res = (res * x) % MOD;
        }
        x = (x * x) % MOD;
        n >>= 1;
    }
    return (int) res;
}